Introduction to Machine Learning

Unit 11: Decision Trees

1. Introduction

This unit introduces the foundational Decision Tree classifier — the building block for Random Forests, AdaBoost, Gradient Boosting, and more. We learn the top-down greedy CART training algorithm, implement both Gini impurity and Entropy / Information Gain by hand on the Play-Golf dataset, handle continuous features via threshold splits, and discuss the hyperparameters that prevent DT overfitting. We close with a full comparison against kNN and NB.

Learning Objectives

2. Theory

2.1 Decision Tree Anatomy

Predict by routing an observation down a sequence of if/else tests from root to leaf.

Outlook decision tree A decision tree determining whether to play based on outlook, humidity, and wind. Outlook decision tree A simple classification model for deciding whether to play Sunny Overcast Rain High Normal False True Outlook? ROOT · INTERNAL Humidity? Windy? INTERNAL NO decision leaf PLAY decision leaf PLAY decision leaf NO decision leaf Classification rules The tree can be expressed as the following logical conditions: IF Outlook = Overcast → PLAY ELIF Outlook = Sunny AND Humidity = High → NO ELIF Outlook = Sunny AND Humidity = Normal → PLAY ELIF Outlook = Rain AND Windy = False → PLAY ELSE Outlook = Rain AND Windy = True → NO Internal nodes evaluate conditions; terminal nodes provide the final recommendation.

2.2 Top-Down Greedy Training (CART Algorithm)

DT learning is a top-down, recursive, binary-split, greedy procedure:

  1. Start with all \(N\) training samples at the root node.
  2. Find the best split (feature, threshold) that maximizes the weighted decrease in impurity (Gini or Entropy).
  3. Partition the node's data into left/right children using that split.
  4. Recurse on each child until a stopping criterion fires (depth limit, pure node, min samples, etc.).
  5. Each leaf predicts the majority class (classification) or mean value (regression).

2.3 Impurity Measures

Gini Index (CART)
Entropy + IG (ID3/C4.5)
Side-by-Side
\[ G(D) = 1 - \sum_{i=1}^{k} p_i^2 \]

\(p_i\) = proportion of class \(i\) in node \(D\). Range: \(0\) (pure) → \( \frac{k-1}{k}\) (balanced mixing, max for k classes).

Binary example: 70 pos, 30 neg → \(G = 1 - (0.7)^2 - (0.3)^2 = 1 - 0.49 - 0.09 = 0.42\).

\[ H(D) = -\sum_{i=1}^{k} p_i \log_2 p_i, \qquad \text{IG}(D, \text{split}) = H(D_{\text{parent}}) - \sum_{c \in \{\text{L},\text{R}\}} \frac{|D_c|}{|D|} H(D_c) \]

IG = reduction in entropy caused by the split. Range of \(H\): 0 (pure) → \(\log_2 k\) (max). We maximize IG; equivalently, we minimize weighted child entropy.

PropertyGiniEntropy
ComputationFaster (squares, no log)Slower (\(\log_2\) per class)
Range (binary)\([0, 0.5]\)\([0, 1]\) bit
Algorithm familyCART (scikit-learn default)ID3 / C4.5 / C5.0
Empirical differenceTypically produces very similar trees. Entropy can help with severe class imbalance.

2.4 Hand Calculation — Choose the Root Split (Play Golf, Gini)

Parent (root): 9 Yes, 5 No → \(G_{\text{root}} = 1 - (9/14)^2 - (5/14)^2 = 1 - 0.413 - 0.128 = 0.459\). Compute weighted Gini for splitting on each of the 4 categorical features:

Feature →OutlookTemperatureHumidityWindy
Child Gini (weighted) 5/14·G(S) + 4/14·G(O) + 5/14·G(R) 4/14·G(Ht)+6/14·G(Md)+4/14·G(Cl) 7/14·G(Hi)+7/14·G(Nm) 8/14·G(F)+6/14·G(T)
Compute 5/14·0.48 + 4/14·0 + 5/14·0.48 4/14·0.50+6/14·0.44+4/14·0.375 7/14·0.490 + 7/14·0.245 8/14·0.375+6/14·0.50
Weighted Gini 0.3429 ← Best (lowest) 0.4405 0.3675 0.4286

✅ Root-Split Winner

Outlook reduces parent impurity from 0.459 → 0.343, the largest drop of all 4 candidate features. CART therefore makes Outlook the root split. Repeat the same calculation independently on each child to grow deeper.

2.5 Continuous (Numerical) Features — Threshold Splits

For a continuous feature \(X\), sort its unique values, evaluate the midpoint between every pair as a candidate split \(X \le t\) vs. \(X > t\), and pick the \(t\) giving the lowest weighted child Gini.

Feature threshold selection workflow Sorted feature values are used to evaluate candidate thresholds with weighted impurity, then select the threshold with the minimum weighted score for a binary split. Selecting the optimal split threshold Evaluate every candidate boundary and choose the one with the lowest weighted impurity. 1 Start with sorted feature values Feature X values 1 3 4 7 8 10 Sorted in ascending order This defines the possible split boundaries. 2 Generate candidate thresholds Candidate thresholds t 2 3.5 5.5 7.5 9 1 10 Each threshold creates a possible binary partition between adjacent feature values. 3 Evaluate each candidate For every t, compute the weighted impurity: Gweighted = (nL/N) · GL + (nR/N) · GR Compare the resulting score across all five thresholds. 4 Choose the best split t* = argmint Gweighted Binary split: ≤ t* vs > t*

2.6 Stopping Criteria & Regularization Hyperparameters

HyperparameterWhat it doesTypical default / tuning range
max_depthStop growing once tree reaches this depth. Main control vs overfit.None (unlimited); try {3, 5, 8, 12, 20}
min_samples_splitMinimum samples in a node before it is eligible for splitting.2 (default); try {2, 5, 10, 20}
min_samples_leafMinimum samples that must land in each resulting leaf.1 (default); try {1, 3, 5, 10}
max_featuresNumber of features to randomly subset at each split (Random Forests).{"sqrt", "log2", d, 0.3·d}
ccp_alpha (pruning)Cost-complexity pruning. Higher α → aggressively prune small branches post-hoc.0.0; search via path

2.7 DT vs. kNN vs. NB — Grand Comparison

DimensionkNN (k=5)Naive BayesDecision Tree (depth 5)
Scaling required?✅ YES (critical for distance)Depends (Gaussian yes, MNB no)❌ NO (invariant to monotonic scaling)
Handles interactions?Implicitly via distance❌ No (independence)✅ Yes (hierarchical splits)
InterpretabilityLow (black-box distances)Medium (odds ratios)✅ High (if/then rules, feature_importances_)
Categorical featuresNeeds OHE/Gower✅ Native (MultinomialNB)OHE or ordinal (HistGradientBoosting native)
Prediction latencySlow O(n·d)Fast O(d)Fast O(depth)
Overfitting riskLow (kNN is stable)✅ Very low (high bias)⚠ High (unlimited depth → memorizes)

3. Interactive Examples

Example 1: Gini & Entropy Calculations

A node contains 60 class-A samples and 40 class-B samples.

(a) Compute Gini.

\(G = 1 - 0.6^2 - 0.4^2 = 1 - 0.36 - 0.16 = \mathbf{0.48}\)

(b) Compute Entropy (bits).

\(H = -0.6 \log_2 0.6 - 0.4 \log_2 0.4 \approx -0.6(-0.737) -0.4(-1.322) \approx 0.442 + 0.529 = \mathbf{0.971}\) bits.

Example 2: Information Gain of a Split

Parent node (A=60, B=40) from Ex. 1 is split into: Left child (A=50, B=10) and Right child (A=10, B=30).

Compute Entropy-based Information Gain of this split.

H(parent) ≈ 0.971 bits (from Ex. 1b).

H(Left) = −5/6·log₂(5/6) −1/6·log₂(1/6) ≈ 0.650 bits. |L|/N = 60/100 = 0.6.

H(Right) = −1/4·log₂(1/4) −3/4·log₂(3/4) ≈ 0.811 bits. |R|/N = 0.4.

Weighted child H = 0.6·0.650 + 0.4·0.811 ≈ 0.714 bits.

IG = H(parent) − weighted H(children) = 0.971 − 0.714 = 0.257 bits.

Example 3: Tracing a Prediction + Reading Rule Path

Use the tree diagram in §2.1. Predict Play for Outlook=Sunny, Temp=Hot, Humidity=High, Windy=False.

  1. Root: Outlook = Sunny → descend left child (Humidity ?).
  2. Humidity = High → take High branch → leaf = NO.
Final prediction: No (don't play). The temperature and wind features were not even queried by this particular tree for this sample!

4. Numerical Solutions

Problem 1: Choose the Best Binary Split on a Numeric Feature

A candidate numeric feature X has values [1, 3, 4, 7] with labels [+, −, +, +]. Parent G = 0.375.

Evaluate two candidate thresholds \(t \in \{2, 5\}\) (X ≤ t vs. X > t) using weighted Gini. Pick the better split and compute its Gini decrease.

📘 Step-by-Step Solution

Step 1: t = 2. Left: {1=+} (pure, G=0), size 1/4. Right: {3=−,4=+,7=+}, GR = 1 − (1/3)² − (2/3)² ≈ 0.444, size 3/4. Weighted G = 0.25·0 + 0.75·0.444 ≈ 0.333.

Step 2: t = 5. Left: {1=+, 3=−, 4=+}, GL = 1 − (2/3)² − (1/3)² ≈ 0.444, size 3/4. Right: {7=+}, GR = 0, size 1/4. Weighted G = 0.75·0.444 + 0.25·0 ≈ 0.333.

Step 3: Both splits tie in weighted Gini (0.333). Both give a decrease of 0.375 − 0.333 = 0.042. A tie-breaking rule (lower index feature / leftmost threshold) picks one.

Problem 2: Effect of max_depth on Overfitting

You train two trees on Adult Census (26K train rows): Tree A (max_depth = 3) → train-AUC 0.86, test-AUC 0.855. Tree B (max_depth = None, unlimited) → train-AUC 0.998, test-AUC 0.84.

📘 Diagnostics & fix

Diagnosis: Tree A = healthy low-bias/moderate-variance fit (tiny 0.005 train–test gap). Tree B = severe overfitting: train AUC near-perfect, test AUC worse than Tree A by 1.5 points.

Fix: Limit capacity via one or more of:

  • Reduce max_depth (GridSearch {2..10}) — single strongest lever.
  • Increase min_samples_leaf to {5, 10, 20} so leaves can't memorize small pockets.
  • Apply Cost-Complexity Pruning (tune ccp_alpha).
  • OR: move to an ensemble (Random Forest / Gradient Boosting) — they solve DT overfitting architecturally (next units!).

Problem 3: Feature Importances from Split Counts

A small tree has 5 splits total: feature A used 3 times (weighted Gini decreases of 0.40, 0.30, 0.10), feature B used 2 times (decreases 0.25, 0.05), feature C never used. Compute normalized feature importances.

📘 Step-by-Step

Total decrease = (0.40+0.30+0.10) + (0.25+0.05) + 0 = 1.10.

Importances: A = 0.80/1.10 ≈ 72.7 %, B = 0.30/1.10 ≈ 27.3 %, C = 0 %. (These sum to 1.0. scikit-learn normalizes the total impurity decrease exactly this way.)

5. Try It Yourself

Problem 1 — Gini for 3 Classes

Node has classes {A:5, B:3, C:2}. Compute Gini impurity.

\(G = 1 - (0.5)^2 - (0.3)^2 - (0.2)^2 = 1 - (0.25+0.09+0.04) = 1 - 0.38 = \mathbf{0.62}\). (Max possible Gini for k=3 is \(2/3 \approx 0.667\) — this node is close to uniform mixing.)
Problem 2 — Weighted Child Gini (2-Way Split)

Split a 20-sample parent into Left (12 samples: 10 pos, 2 neg) and Right (8 samples: 1 pos, 7 neg). Compute weighted Gini of the split and compare it to parent G = 0.48. Did purity improve? By how much?

GL = 1 − (10/12)² − (2/12)² ≈ 0.278; GR = 1 − (1/8)² − (7/8)² ≈ 0.219.
Weighted Gini = 0.6·0.278 + 0.4·0.219 ≈ 0.254.
Purity improved by 0.480 − 0.254 = 0.226 (large drop → good split!).
Problem 3 — Overfitting Diagnosis

Tree-C has max_depth=10, min_samples_leaf=1. Its train accuracy = 0.998 but test accuracy = 0.712 on the same task as Problem 2 of §4.

(i) What is this phenomenon? (ii) Name 3 knobs to fix it.

(i) Severe overfitting (memorization of training-set noise).

(ii) Any three valid regularizers from: lower max_depth, higher min_samples_leaf, higher min_samples_split, max_features (if ensembling), ccp_alpha cost-complexity pruning, early stopping, switching to a Random Forest / Gradient Boosting ensemble.

6. Interactive Quiz

Answer all 5 MCQs. Click on an option to get instant feedback.

Your score: 0 / 5

7. Key Takeaways

  1. CART = Top-down greedy binary splits. At each node, sweep every (feature, threshold) pair; keep the one minimizing weighted child Gini (Entropy, MSE, MAE for regression).
  2. Gini vs. Entropy rarely produce materially different trees. Gini is faster default; Entropy/IG can help with heavy imbalance or when using information-theoretic justifications.
  3. Numeric features → try every midpoint as threshold and pick the best binary split (X ≤ t vs. > t). This is why DTs are scale-invariant: only the order matters.
  4. DTs overfit unless you regularize. Unlimited-depth DTs memorize noise. The single most effective lever: max_depth. Combine with min_samples_leaf and optionally ccp_alpha pruning.
  5. D strengths: No scaling, native handling of mixed types (with OHE or HistGBT), interpretable rules, built-in feature importances, fast prediction. Weakness: high variance → unstable trees. Solution: ensembles!
  6. Grand comparison: NB fastest/baseline & text king; kNN simplest lazy distance method; DTs best for rule-based interpretability and strong tabular baselines. Enemies of DT: deep unlimited trees, tiny leaf samples.

8. Common Pitfalls

  1. Training unlimited-depth DTs on default scikit-learn settings. This almost always overfits. Always set max_depth at a minimum.
  2. Using Gini / Entropy on regression trees. For regression, split on MSE / MAE reduction — not Gini. scikit-learn's DecisionTreeRegressor does this.
  3. Dropping feature names / not plotting the tree. DTs are interpretable by design — leverage this! Use tree.plot_tree or export_graphviz.
  4. One-hot encoding high-cardinality categorical features into a deep CART tree. This creates imbalanced splits and blows up depth. Use HistGradientBoostingClassifier's categorical_features or target encoding instead.
  5. Believing feature_importances_ measure causal importance. They measure correlation-driven impurity reduction on the training set. Two correlated features can split credit arbitrarily. Use permutation importance + SHAP for robust interpretations.
  6. Comparing DT (single) against a tuned ensemble and concluding "trees are bad." Single trees are the weak learner. The power of DTs is as base learners inside Random Forest / Gradient Boosting.

9. Resources